package com.sali.DP;

/**
 连续子数组的最大和(二)
 */
public class JZ_85 {

    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxSum = array[0];
        int left = 0;
        int right = 0;
        int leftRes = 0;
        int rightRes = 0;
        for ( int i = 1; i < array.length; i++ ) {
            right++;
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            if ( dp[i-1] + array[i] < array[i] ) {
                left = i;
            }
            if ( dp[i] > maxSum || (dp[i] == maxSum && right - left + 1 > rightRes - leftRes + 1) ) {
                maxSum = dp[i];
                rightRes = right;
                leftRes = left;
            }
        }
        int[] res = new int[rightRes - leftRes + 1];
        for ( int i = leftRes; i <= rightRes; i++ ) {
            res[i - leftRes] = array[i];
        }
        return res;
    }

}
